package com.kevinkk.dp;

/**
 * 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
 */

/**
 * dp 公式：
 * if (sChar[i - 1] == tChar[j - 1]) {
 *      // 如果 相等，那么刚好 dp 数组长度加1
 *      dp[i][j] = dp[i - 1][j - 1] + 1;
 * } else {
 *      // 否则，尝试删除 t 字符串中的一个元素再进行一次比较
 *      dp[i][j] = dp[i][j - 1];
 * }
 */

public class IsSubsequence {
    class Solution {
        public boolean isSubsequence(String s, String t) {
            char[] sChar = s.toCharArray(), tChar = t.toCharArray();
            int[][] dp = new int[sChar.length + 1][tChar.length + 1];
            int max = 0;

            for (int i = 1; i <= sChar.length; i++) {
                for (int j = 1; j <= tChar.length; j++) {
                    if (sChar[i - 1] == tChar[j - 1]) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    } else {
                        dp[i][j] = dp[i][j - 1];
                    }
                    max = Math.max(max, dp[i][j]);
                }
            }
            // 如果 最长相等字符串的长度和 s 字符串的长度相同，代表是子串
            return max == sChar.length;
        }
    }
}
